package com.atguigu.pa;

import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {3,1,5,4,7,6,2};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void insertSort(int[] arr) {
        for(int i = 1 ; i< arr.length ; i++){
            //num表示待插入的牌
            int num = arr[i];
            //index表示待插入的位置
            int index = i ;
            for(int j = i-1 ; j>=0 ; j--){
                //如果待插入的牌比当前比较位置的牌要小。
                if(num<arr[j]){
                    //则将这个位置的牌往后挪，空出这个位置
                    arr[j+1] = arr[j];
                    //用index记录新的空出来的位置
                    index = j;
                }
            }
            //比较完之后，将新抓的牌插入到空位置
            arr[index] = num ;
        }
    }
}
